Pseudo-noise ("PN") codes are finding increasing application, for example in the area of wireless telephony. In code division multiple access telephony, for example, a digitized data stream is encoded using PN codes, to "spread" the spectrum of the signal transmitting the data. The digitized data stream is decoded using the same PN code used to encode it at the transmitter.
PN codes are generated by pseudo-noise sequence generators ("PNSGs"). One familiar apparatus used in PNSGs is a device known as a linear feedback shift register ("LFSR"). However, PNSGs are not limited to LFSRs. An PNSG is typically composed of a series of N stages, each stage including a memory stage or memory step, depending on whether the PNSG is hardware (e.g., an LFSR) or software, whose inputs are a linear combination (modulo 2) of the PNSG itself and of the previous memory stage or step when viewed from a left-to-right perspective. The individual ones and zeros ("bits") of the output sequence of a PNSG, which is the PN code, are sometimes referred to as "chips." A specific example of a PNSG 1 for N=4 is shown in FIG. 1. It will be understood that the PNSG 1 may be implemented in hardware, in which case FIG. 1 represents an LFSR, or it may be implemented in software, for example for execution on a DSP, in which case FIG. 2 represents a structure for the logical flow of the method so implemented. While discussion is in terms of such method, i.e., with "steps" instead of "stages"it will be understood that selection of hardware or software for implementation is well within the design choices of which the routineer in the art is capable, once the principles of the present invention described herein are understood. In general, hardware is to be preferred, because of its speed. However, full or partial implementation in software may be desirable for other considerations, such as cost.
In FIG. 1 can be seen the four memory steps 50, 52, 54, 56, as well as a logical XOR step 58 disposed between memory steps 54 and 56. Logical XOR steps implement a modulo-2 addition. The output of memory step 50 is provided to the input of memory step 52, the output of memory step 52 is provided to the input of memory step 54, while the output of memory step 54 is provided to one input of logical XOR step 58. The output of logical XOR step 58 is provided to the input of memory step 56, with the output 60 of the PNSG being the output 60 of memory step 56. A feedback path 60' is also provided from the output 60 of memory step 56 to the input of memory step 50 and to the other input of logical XOR step 58.
The operation of the PNSG 1 shown in FIG. 1 can be described by either a state diagram or a table. The "state" of the PNSG 1 is the value of the bits stored in the memory steps before a given iteration. Thus, for PNSG 1, the state before iteration "n" may be expressed as S.sub.n =pqrs, where p, q, r and s are the values of the bits stored in memory steps 56, 54, 52, 50, respectively. If the memory steps 56, 54, 52, 50, of PNSG 1 are initialized with the state S.sub.0 =1000, the output and subsequent states of the PNSG are as shown in Table 1:
TABLE 1 ______________________________________ Clock Cycle or Iteration State Output ______________________________________ 0 1000 1 1 1001 1 2 1011 1 3 1111 1 4 0111 0 5 1110 1 6 0101 0 7 1010 1 8 1101 1 9 0011 0 10 0110 0 11 1100 1 12 0001 0 13 0010 0 14 0100 0 15 1000 1 ______________________________________
With respect to Table 1, note that after the 15th iteration the state of the PNSG reaches that of the initial or 0th iteration. In fact, the output and state sequences of the PNSG repeat with a period of 15. For the case of N=4, this represents the maximum possible period since the all zeros state never occurs. Thus, in general, a PNSG is capable of generating a sequence of period (or, length) 2.sup.N -1, where N is the number of steps. Not all PNSG configurations generate a sequence with the largest possible period, but those that do are said to generate a maximal length sequence or "m-sequence" for short. For the purposes of the present invention, PNSGs that generate m-sequences are of primary interest and hence discussion herein is focused on PNSGs having this property.
Now, it is often desirable to generate a delayed version of a PN code relative to some master, or reference, sequence. While it is possible to use a simple delay line to accomplish this, it is frequently necessary to generate very long delays that cause this approach to become impractical.
A superior technique for generating a delayed PN code exploits the shift-and-add property of m-sequences. This property is that when a shifted or delayed version of a PN code is added to itself, the resulting code is merely a delayed version of the original. To better understand this, consider the following sequence generated by the PNSG 1 of FIG. 1:
. . 1111010110010000 . . . .
If this sequence is shifted or delayed by one chip, the result is
. . 011110101100100 . . . .
Adding these two sequences together using modulo 2 arithmetic yields
. . 100011110101100 . . . ,
which is merely the original PN sequence delayed by 4 chips. While other specific delays can be generated in this fashion, a more efficient and sophisticated method is described next.
Referring to the State column in Table 1, note that the sequence associated with a particular stage represents a shifted version of the PNSG output. E.g., the sequence corresponding to the least significant bit of the state vector is identical to the output; the sequence corresponding to the most significant bit is the output shifted by one chip, etc. Thus according to the shift-and add property of m-sequences, another PN code having a specific shift relative to the original sequence can be generated by adding together one or more outputs of the four stages. If the PN code is being provided serially in time, then that shift represents a delay.
FIG. 2 shows a PN sequence generator similar to the arrangement of FIG. 1, including a PNSG 1 like that of FIG. 1, but, unlike the arrangement of FIG. 1, also having an associated delay element 62. As in FIG. 1, four memory steps 50, 52, 54, 56, a logical XOR step 58, an output 60 and a feedback path 60' are provided, interconnected as in FIG. 1. Also provided, however, is delay element 62. The delay element 62 is comprised of an additional four memory steps 64, 66, 68, and 70, and associated logical AND and logical XOR steps, as explained below. The memory steps 64, 66, 68, and 70, receive a PN shift-and-add mask value over an input 72. The output of memory step 64 is provided to one input of a first logical AND step 74. Logical AND steps perform a modulo-2 multiplication. The other input of logical AND step 74 is the output of memory step 50. The output of memory step 66 is provided to one input of a second logical AND step 76. The other input of logical AND step 76 is the output of memory step 52. The output of memory step 68 is provided to one input of a third logical AND step 78. The other input of logical AND step 78 is the output of memory step 54. The output of memory step 70 is provided to one input of a fourth logical AND step 80. The other input of logical AND step 80 is the output of memory step 56.
The output of logical AND step 74 is provided to one input of a second logical XOR step 82. The output of logical AND step 76 is provided to the second input of logical XOR step 82, while the output of logical XOR step 82 is provided to one input of a third logical XOR step 84. The output of logical AND step 78 is provided to the second input of logical XOR step 84, while the output of logical XOR step 84 is provided to one input of a fourth logical XOR step 86. The output of logical AND step 80 is provided to the second input of logical XOR step 86. The output 88 of logical XOR step 86 provides the same sequence as the output 60 of the PNSG 1, but delayed by an amount determined by the value of the shift-and-add mask stored in memory steps 64, 66, 68, and 70.
Thus, by forming the inner product of a shift-and-add mask, hereinafter simply referred to as a "mask," stored in the memory steps 64, 66, 68, 70, with the states of the PNSG, stored in the memory steps 50, 52, 54, 56, as shown in FIG. 1, a second sequence can be generated with a known delay relative to the PNSG output. This second sequence is, as mentioned above, provided at the output 88 of logical XOR step 86.
However, a problem that exists in the practical application of the use of a mask for accomplishing rapid shifts of PN sequences is in the time it takes to generate the mask itself. For example, PN sequence generators are currently being used in code division multiple access ("CDMA") cellular telephone applications. Rapid shifts in the PN sequences generated in such applications are desirable for despreading a desired PN delay. Therefore, there is a need for a method and apparatus for generating a mask rapidly, yet controllably and accurately.